//跳跃游戏 || 
//https://leetcode.cn/problems/jump-game-ii/?envType=study-plan-v2&envId=top-interview-150
class Solution {
public:
    int jump(vector<int>& nums) 
    {
        int n = nums.size();
        if(n == 1) return 0;

        int ret = 0;
        int pos = 0;
        while(1)
        {
            //一次跳跃
            ret++;

            //计算所有可以跳跃的位置，选其中可以跳的最远距离下标为新的下标
            int maxlen = INT_MIN;
            int begin = pos;
            for(int i = 1; i <= nums[begin]; i++)
            {
                int dest = begin + i;
                if(dest >= n - 1) return ret;

                if(nums[dest] == 0) continue;

                if(maxlen < dest + nums[dest])
                {
                    maxlen = dest + nums[dest];
                    pos = dest;
                }
            }
        }
        
        return ret;
    }
};
};